#include<iostream>
#include<string>
#include<fstream>
#include<map>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;
struct ll_edge
{
	unsigned int id;
	ll_edge* next;
	int weight;
	ll_edge(unsigned int v, int w_val)
	{
		id = v;
		next = NULL;
		weight = w_val;
	}
};

struct ll_node
{
	unsigned int id;
	ll_edge* fe;
	ll_node(unsigned int v)
	{
		id = v;
		fe = NULL;
	}
};

class ll_graph
{
public:
	vector<ll_node*> g;
	unordered_map<unsigned int, unsigned int> index;
	int N;
	int n;
	ll_graph()
	{
		N=0;
		n=0;
	}
	~ll_graph()
	{
		for(int i=0;i<g.size();i++)
		{
			ll_edge* tmp = g[i]->fe;
			ll_edge* to_delete = tmp;
			while(tmp)
			{
				to_delete = tmp;
				tmp = tmp->next;
				delete to_delete;
			}
		}
		g.clear();
		vector<ll_node*>().swap(g);
		index.clear();
		unordered_map<unsigned int, unsigned int>().swap(index);
	}
	int insert(unsigned int s, unsigned int d, int weight);
	int query(unsigned int s, unsigned int d);
	void successor(unsigned int v, vector<unsigned int> &vec);
	void delete_node(unsigned int v, map<unsigned int, int> &removed_edges);
};

int ll_graph::insert(unsigned int s, unsigned int d, int weight)
{
	unordered_map<unsigned int, unsigned int>::iterator it = index.find(s);
	int p = 0;
	if(it==index.end())
	{
		p = g.size();
		index[s] = p;
		ll_node* f = new ll_node(s);
		g.push_back(f);
		n++;
	}
	else
		p = it->second;
	ll_edge* tmp = g[p]->fe;
	bool find = false;
	while(tmp)
	{
		if(tmp->id==d)
		{
			find = true;
			tmp->weight += weight;
			break;
		}
		tmp = tmp->next;
	}
	if(!find)
	{
		ll_edge* e = new ll_edge(d, weight);
		e->next = g[p]->fe;
		g[p]->fe = e;
		N++;
		return 1;
	}
	return 0;
}
int ll_graph::query(unsigned int s, unsigned int d)
{
	unordered_map<unsigned int, unsigned int>::iterator it = index.find(s);
	if(it==index.end())
		return 0;
	else
	{
		int p = it->second;
		ll_edge* e= g[p]->fe;
		while(e)
		{
			if(e->id==d)
				return e->weight;
			e=e->next;
		}
		return 0;
	}
}
void ll_graph::successor(unsigned int v, vector<unsigned int> &vec)
{
	unordered_map<unsigned int, unsigned int>::iterator it = index.find(v);
	if(it==index.end())
			return;
	else
	{
			unsigned int p = it->second;
			ll_edge* e= g[p]->fe;
			while(e)
			{
				vec.push_back(e->id);
				e=e->next;
			}
			return;
	}
}

void ll_graph::delete_node(unsigned int v, map<unsigned int, int> &removed_edges)
{
	unordered_map<unsigned int, unsigned int>::iterator it = index.find(v);
	if(it==index.end())
			return;
		else
		{
			unsigned int p = it->second;
				ll_edge* e= g[p]->fe;
				ll_edge* to_delete = e;
				while(e)
				{
					removed_edges[e->id]=e->weight;
					to_delete = e;
					e=e->next;
					delete to_delete;
					N--;
				}
				g[p]->fe = NULL;
				return;
		}
}


struct icl_edge
{
	unsigned int s;
	unsigned int d;
	icl_edge* s_next;
	icl_edge* d_next;
	int weight;
};
struct icl_node
{
	unsigned int ID;
	icl_edge* src_el;
	icl_edge* dst_el;
};
class icl_graph
{
	private:
		int n;
		int N;

	public:
		int chong;
		map<unsigned int, int> index;

		vector<icl_node*> g;
		icl_graph();
		~icl_graph();
		void update(unsigned int s1, unsigned int s2,int weight);
		int query(unsigned int s1, unsigned int s2);
		int	get_nodenum();
		int get_edgenum();
		void successor(unsigned int v, vector<unsigned int> &vec);
		void precursor(unsigned int v, vector<unsigned int> &pre);
 };
 icl_graph::icl_graph()
 {
 	n=0;
 	N=0;
 }
 icl_graph::~icl_graph()
 {
	 for(int i=0;i<g.size();i++)
	 		{
	 			icl_edge* tmp = g[i]->src_el;
	 			icl_edge* next = tmp;
	 			while(tmp)
	 			{
	 				next = tmp->s_next;
	 				delete tmp;
	 				tmp = next;
	 			}
	 		}
	 		g.clear();
	 		vector<icl_node*>().swap(g);
	 		index.clear();
 }
 int icl_graph::get_nodenum()
 {
 	return n;
 }
 int icl_graph::get_edgenum()
 {
 	return N;
 }
void icl_graph::update(unsigned int s1, unsigned int s2, int weight)
 {
 		int n1;
 		map<unsigned int,int>::iterator it;
 		it = index.find(s1);
		if(it!=index.end())
			n1 = it->second;
		else
		{
			index[s1]=n;
			n1=n;
			n++;
			icl_node *e=new icl_node;
			e->src_el = NULL;
			e->dst_el = NULL;
			e->ID = s1;
			g.push_back(e);
		}

		int n2;
		it = index.find(s2);
		if(it!=index.end())
			n2 = it->second;
		else
		{
			index[s2] = n;
			n2 = n;
			n++;
			icl_node* e = new icl_node;
			e->src_el = NULL;
			e->dst_el = NULL;
		 	e->ID = s2;
		 	g.push_back(e);
		}


		icl_edge* e=g[n1]->src_el;
		bool find = false;
		while(e)
		{
			if(e->d==s2)
			{
				e->weight+=weight;
				find = true;
				break;
			}
			e=e->s_next;
		}
		if(!find)
		{
			N++;
			icl_edge* f=new icl_edge;
			f->s = s1;
			f->d = s2;
			f->weight = weight;
			f->s_next = g[n1]->src_el;
			g[n1]->src_el = f;
			f->d_next = g[n2]->dst_el;
			g[n2]->dst_el = f;
		}
 }
 int icl_graph::query(unsigned int s1, unsigned int s2)
 {
 	map<unsigned int,int>::iterator it;
 	int n1;
 	it = index.find(s1);
	if(it!=index.end())
		n1 = it->second;
	else return 0;
	icl_edge* e = g[n1]->src_el;
	while(e!=NULL)
	{
		if(e->d==s2)
			return e->weight;
		e = e->s_next;
	}
		if(e==NULL)
 		return 0;
 }

void icl_graph::successor(unsigned int v, vector<unsigned int> &vec)
{
	map<unsigned int, int>::iterator it;
	int n1;
	it = index.find(v);
	if(it!=index.end())
		n1 = it->second;
	else return;
	icl_edge* e = g[n1]->src_el;
	while(e!=NULL)
	{
		vec.push_back(e->d);
		e= e->s_next;
	}
	return;
}

void icl_graph::precursor(unsigned int v, vector<unsigned int> &pre)
{
	map<unsigned int, int>::iterator it;
	int n1;
	it = index.find(v);
	if(it!=index.end())
		n1 = it->second;
	else return;
	icl_edge* e = g[n1]->dst_el;
	while(e!=NULL)
	{
		pre.push_back(e->s);
		e= e->d_next;
	}
	return;
}



